package leecode

import "sort"

func combinationSum2(candidates []int, target int) (result [][]int) {
	var backtracking func(target, startIndex int, used []bool)
	sort.Ints(candidates)
	path := make([]int, 0, len(candidates))
	backtracking = func(target, startIndex int, used []bool) {
		if target <= 0 {
			if target == 0 {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
			}
			return
		}
		for i := startIndex; i < len(candidates); i++ {
			// 树层去重 , candidates[i] == candidates[i-1] 时 , 去判断重复使用的元素不是在同一个树枝上
			if i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false {
				continue
			}
			target -= candidates[i]
			path = append(path, candidates[i])
			used[i] = true //当前元素被使用过了
			backtracking(target, i+1, used)
			used[i] = false
			target += candidates[i]
			path = path[:len(path)-1]
		}
	}
	used := make([]bool, 0, len(candidates))
	used = append(used, false)
	backtracking(target, 0, used)
	return
}
